package lew.bing.exp.alg;

import java.util.Iterator;
import java.util.Stack;

/**
 * Created by 刘国兵 on 2018/8/26.
 */
public class BinaryTree<T extends Key<V>,V extends Comparable<V>> implements Iterable<T> {

    // 按照添加的顺序中序遍历
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            private Stack<Node> stack = new Stack<>();

            {
                Node n = root.left;
                while (n != null) {
                    stack.push(n);
                    n = n.left;
                }
            }

            @Override
            public boolean hasNext() {
                return !stack.isEmpty();
            }

            @Override
            public T next() {
                Node pop = stack.pop();
                // 将右边的所有左节点放进栈中
                Node n = pop.right;
                while (n != null) {
                    stack.push(n);
                    n = n.left;
                }
                return pop.value;
            }
        };
    }

    private class Node {
        // 遍历需要放在这里才行
        T value;
        Node left;
        Node right;
        Node(T value) {
            this.value = value;
        }
    }

    Node root;
    public BinaryTree() {
        root = new Node(null);// root始终为null，并且子节点有且只有左节点
    }

    public boolean isEmpty() {
        return root.left == null;
    }

    public void add(T value) {
        if (value == null || value.value() == null) {
            throw new NullPointerException();//不允许添加空值
        } else {
            Node n = root;
            Node m = root;
            boolean left = true;
            while (n != null) {
                m = n;
                if (n.value == null
                        || value.value().compareTo(n.value.value()) < 0) {// 表明是根
                    n = n.left;
                    left = true;
                } else {
                    n = n.right;
                    left = false;
                }
            }
            if (left) {
                m.left = new Node(value);
            } else {
                m.right = new Node(value);
            }
        }
    }

    public T find(V key) {
        Node m = root.left;
        while (m != null && !key.equals(m.value.value())) {
            if (m.value == null || m.value.value().compareTo(key) > 0) {
                m = m.left;
            } else {
                m = m.right;
            }
        }
        if (m == null) {
            return null;
        } else {
            return m.value;
        }

    }

    public static void main(String[] args) {
        BinaryTree<ForTest, Integer> tree = new BinaryTree<>();
        tree.add(new ForTest(3,"3"));
        tree.add(new ForTest(1,"1"));
        tree.add(new ForTest(4,"4"));
        tree.add(new ForTest(2,"2"));
        System.out.println(tree.find(2));
        for (ForTest t: tree) {
            System.out.println(t);
        }
    }

    private static class ForTest implements Key<Integer> {

        private Integer value;
        private String name;

        public ForTest(int value,String name) {
            this.value = value;
            this.name = name;
        }

        @Override
        public Integer value() {
            return value;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "ForTest{" +
                    "value=" + value +
                    ", name='" + name + '\'' +
                    '}';
        }
    }



}
